package tree_map_set;

import java.util.HashSet;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86187
 * Date: 2022-08-21
 * Time: 14:36
 */

public class TestHomeWork {

    /**
     *  前K个高频词汇：
     *  给定一个单词列表words和一个整数 k ，
     *  返回前k个出现次数最多的单词。
     * 返回的答案应该按单词出现频率由高到低排序。
     * 如果不同的单词有相同出现频率， 按字典顺序 排序。
     *
     */
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        //1.统计单词出现的次数
        for (String str : words) {
            int val = map.getOrDefault(str,0); //返回 key 对应的 value，key 不存在，返回默认值

            map.put(str,val+1);
        }

        //2.建立大小为k 的小根堆（降序）
        PriorityQueue< Map.Entry<String,Integer> > minQ = new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override                                                       //传了一个参数k
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {

                //频率相同时 把它变成以 key 为准的大根堆
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }

                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //3.遍历map(此时 key 与 value 是一个整体) 放满小根堆 然后从k+1 个开始与堆顶元素进行比较
        for(Map.Entry<String,Integer> entry : map.entrySet()) { //此时 key 与 value 是一个整体
            //3.如果小根堆没有放满 直接放进去
            if(minQ.size() < k) {
                minQ.offer(entry);
            }else {
                //4.如果小根堆放满了 从k+1 个元素开始与堆顶元素进行比较
                Map.Entry<String,Integer> top = minQ.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minQ.poll();
                    minQ.offer(entry);
                }else {
                    // < 或 == 的情况 只需要处理 == 的情况
                    if(top.getValue().compareTo(entry.getValue()) == 0) {
                        //不同的单词有相同出现频率， 按字典顺序 排序。
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minQ.poll();
                            minQ.offer(entry);
                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for(int i = 0; i < k; ++i) {
            Map.Entry<String,Integer> top = minQ.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret); //逆置

        return ret;
    }

    public static void main(String[] args) {
        String[] str = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        System.out.println(topKFrequent(str,3));
    }

    /**
     *  给定一个非空整数数组，除了某个元素只出现一次以外，
     *  其余每个元素均出现两次。找出那个只出现了一次的元素。
     */
    public static int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0; i < nums.length; ++i) {
            ret ^= nums[i];
        }
        return ret;
    }

    public static int singleNumber2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length;++i) {
            int key = nums[i];
            if(!set.contains(key)) {
                set.add(key);
            }else {
                set.remove(key);
            }
        }
        //走到这说明 集合里只有一个元素 需要再次遍历才可以找到它
        for(int i = 0; i < nums.length;++i) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

    public static void main1(String[] args) {
        int[] array = { 1,3,5,5,3,1,7};
        System.out.println(singleNumber(array));
        System.out.println(singleNumber2(array));



    }
}
